package com.dyz.swordFingerOffer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author: daiyizheng
 * @date: 2021/6/11 21:29
 * @description:
 */
public class Print32_3 {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if(pRoot==null){
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int sum =1;
        int  num = 1;
        while(!queue.isEmpty()){
            ArrayList<Integer> arr = new ArrayList<>();
            int pre = 0;

            while(sum>0){
                TreeNode node = queue.poll();
                arr.add(node.val);

                if(node.left!=null){
                    queue.add(node.left);
                    pre++;
                }
                if(node.right!=null){
                    queue.add(node.right);
                    pre++;}
                sum--;
            }
            if(num%2==0){
                for (int i =0, j = arr.size()-1; i<j;i++,j--){
                    int res = arr.get(i);
                    arr.set(i, arr.get(j));
                    arr.set(j, res);
                }
            }
            ans.add(arr);
            sum = pre;
            num++;

        }
        return ans;
    }


    //双栈实现
    public ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>>  res  = new  ArrayList<ArrayList<Integer>>();
        if(pRoot==null){return  res;}
        Stack<TreeNode> stack1 =  new  Stack<>();
        stack1.push(pRoot);
        Stack<TreeNode>  stack2 =  new Stack<>();
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(!stack1.isEmpty()){
                ArrayList<Integer>  tmp  = new  ArrayList<>();
                while(!stack1.isEmpty()){
                    TreeNode  p  =  stack1.pop();
                    tmp.add(p.val);
                    if(p.left!=null){
                        stack2.add(p.left);}
                    if(p.right!=null){
                        stack2.add(p.right);}
                }
                res.add(tmp);
            }else{
                ArrayList<Integer>  tmp  = new  ArrayList<>();
                while(!stack2.isEmpty()){
                    TreeNode p =  stack2.pop();
                    tmp.add(p.val);
                    if(p.right!=null){
                        stack1.add(p.right);
                    }
                    if(p.left!=null){
                        stack1.add(p.left);
                    }
                }
                res.add(tmp);
            }
        }
        return  res;
    }
}
